#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
int Threemid(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
    }
    else {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[right] > a[left])
        {
            return left;
        }
        else
            return right;
    }
    return left;
}
int  _QuickSork(int* a, int left, int right)
{
    //三数取中
    int mid = Threemid(a, left, right);
    swap(&a[mid], &a[left]);
    //右边找小，左边找大
    int key = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
        while (left < right && a[left] <= a[key])
        {
            left++;
        }
        swap(&a[left], &a[right]);
    }
    swap(&a[key], &a[left]);
    return left;
}
void QuickSort(int* a, int begin, int end)
{
    if (begin >= end)
    {
        return;
    }
    int mid = _QuickSork(a, begin, end);
    //[begin mid-1] [mid+1  end]
    QuickSort(a, begin, mid - 1);
    QuickSort(a, mid + 1, end);
}
void _MergeSort(int* a, int* tmp, int begin, int end)
{
    if (begin >= end)
    {
        return;
    }
    //分为两步  1.分解  2.合并
    //分解
    int mid = (begin + end) / 2;
    //[begin mid][mid+1 end]
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);
    //合并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int mark = 0;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[mark++] = a[begin1++];
        }
        else
        {
            tmp[mark++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[mark++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[mark++] = a[begin2++];
    }
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int begin, int end)
{
    int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
    _MergeSort(a, tmp, begin, end);
    free(tmp);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
    //希尔排序
    *returnSize = numsSize;
    //    int gap = numsSize;
    //  while(gap>1)
    //  {
    //      gap = gap/3+1;
    //      for(int i = 0;i<numsSize-gap;i++)
    //     {
    //             int end = i;
    //         int tmp  = nums[end+gap];
    //         while(end>=0)
    //         {
    //             if(nums[end]>tmp)
    //             {
    //                 nums[end+gap] = nums[end];
    //             }
    //             else
    //             {
    //                 break;
    //             }
    //             end-=gap;
    //         }
    //         nums[end+gap] = tmp;
    //     }

    //  }

    // //堆排序
    // void AjustDown(int * a,int n,int parent)
    // {
    //     int child = parent*2+1;
    //     while(child<n)
    //     {
    //         if(child+1<n&&a[child]<a[child+1])
    //     {
    //         child++;
    //     }
    //     if(a[parent]<a[child])
    //     {
    //         swap(&a[parent],&a[child]);
    //         parent = child;
    //         child = parent*2+1;
    //     }
    //     else
    //     break;
    //     }
    // }
    // //向下调整建堆
    // for(int i = (numsSize-1-1)/2;i>=0;i--)
    // {
    //     AjustDown(nums,numsSize,i);
    // }
    // //向下调整排序
    // for(int i = numsSize-1;i>0;i--)
    // {
    //     swap(&nums[i],&nums[0]);
    //     AjustDown(nums,i,0);
    // }
    //冒泡排序
    // for(int j = 0;j<numsSize;j++)
    // {
    //     for(int i = 1;i<numsSize-j;i++)
    //     {
    //         if(nums[i-1]>nums[i])
    //         {
    //             swap(&nums[i-1],&nums[i]);
    //         }
    //     }
    // }

    //选择排序  错误
    // int begin = 0,end = numsSize-1;
    // while(begin<end)
    // {
    //     int min = begin,max = begin;
    //     for(int i = begin+1;i<=end;i++)
    //     {
    //         if(nums[i]>nums[max])
    //         {
    //             max = i;
    //         }
    //         if(nums[i]<nums[min])
    //         {
    //             min = i;
    //         }
    //     }
    //     swap(&nums[begin],&nums[min]);
    //     if(begin==max)
    //     {
    //         max = min;
    //     }
    //     swap(&nums[end],&nums[max]);
    //     --end;
    //     ++begin;
    //  }
    int begin = 0;
    int end = numsSize - 1;
    // //快速排序
    // QuickSort(nums,begin,end);
    //归并排序
    MergeSort(nums, begin, end);
    return nums;
}